//<p>假设你正在爬楼梯。需要 <code>n</code>&nbsp;阶你才能到达楼顶。</p>
//
//<p>每次你可以爬 <code>1</code> 或 <code>2</code> 个台阶。你有多少种不同的方法可以爬到楼顶呢？</p>
//
//<p>&nbsp;</p>
//
//<p><strong>示例 1：</strong></p>
//
//<pre>
//<strong>输入：</strong>n = 2
//<strong>输出：</strong>2
//<strong>解释：</strong>有两种方法可以爬到楼顶。
//1. 1 阶 + 1 阶
//2. 2 阶</pre>
//
//<p><strong>示例 2：</strong></p>
//
//<pre>
//<strong>输入：</strong>n = 3
//<strong>输出：</strong>3
//<strong>解释：</strong>有三种方法可以爬到楼顶。
//1. 1 阶 + 1 阶 + 1 阶
//2. 1 阶 + 2 阶
//3. 2 阶 + 1 阶
//</pre>
//
//<p>&nbsp;</p>
//
//<p><strong>提示：</strong></p>
//
//<ul>
//	<li><code>1 &lt;= n &lt;= 45</code></li>
//</ul>
//<div><div>Related Topics</div><div><li>记忆化搜索</li><li>数学</li><li>动态规划</li></div></div><br><div><li>👍 2428</li><li>👎 0</li></div>

package com.rising.leetcode.editor.cn;

/**
 * 爬楼梯
 * @author DY Rising
 * @date 2022-05-19 17:25:15
 */
public class P70_ClimbingStairs{
    public static void main(String[] args) {
        //测试代码
        Solution solution = new P70_ClimbingStairs().new Solution();
        long start  = System.currentTimeMillis();
        System.out.println(solution.climbStairs(45));
        long end = System.currentTimeMillis();
        System.out.println(end - start);
    }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int climbStairs(int n) {
        return slidingArray(n);
    }

    /**
     * 抽象出动态规划函数f(i) = f(i-1) + f(i-2)
     * 递归
     * @param n
     * @return
     */
    public int dfs(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        return dfs(n - 1) + dfs(n - 2);
    }

    /**
     * 抽象出动态规划函数f(i) = f(i-1) + f(i-2)
     * 滑动数组
     * @param n
     * @return
     */
    public int slidingArray(int n) {
        if (n<=2) {
            return n;
        }
        int sum = 0, first = 1, second = 2;
        for (int i = 3; i <= n; i++) {
            sum = first + second;
            first = second;
            second = sum;
        }
        return sum;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
